/*
 * Алгоритм Крускала
 */

#include <assert.h>
#include <ctype.h>
#include <limits.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

#ifdef DEBUG
# define debug_fprintf(x)	fprintf x
#else
# define debug_fprintf(x)	((void) 0)
#endif

#define S_assert(st) ((st)?((void)0):(void)fprintf(stderr,"Assertion (soft) \"%s\" in %s:%s():%d: failed.\n",#st,__FILE__,__func__,__LINE__))
#define SWAP_INT(a, b)	(((a) ^ (b)) && ((b) ^= (a) ^= (b), (a) ^= (b)))
#define MIN(a, b)	((a) < (b) ? (a) : (b))
#define MAX(a, b)	((a) > (b) ? (a) : (b))

/* queue */
struct queue {
	char *data;
	size_t _data_size;

	int head;
	int n;
	int _max;
};

/* stack */
struct stack {
	char *data;
	size_t n; /* how many elements in the stack atm */
	size_t _data_size; /* size of one element (in bytes) */
	size_t _allocated; /* how much storage is allocated for *data (in bytes) */
	size_t _max; /* maximum storage that we are allowed allocate for *data */
};

/* autoarray */
struct vector {
	char *data;
	size_t _elem_size;

	int n;
	int _max;
};

/* doubly-linked list */
struct dll_node {
	int x, y;
	long long z;
	char *data;
	size_t _data_size;
	struct dll_node *prev, *next;
};

/* priority queue */
struct pqueue {
	char *data; /* threres a reason why i use a continuous array */
	size_t _data_size;

	int n; /* amount of elements in the queue */
	int _max; /* maximum space allocated for .data */
	int (*cmp)(const void *, const void *); /* comaparator function */

	bool _autoexpand; /* trigger autoexpansion on new element insertion */
};

/* graph repr: adjlist w/ doubly-linked list */
enum vertex_st {
	VTX_ST_UNKN = 0,
	VTX_ST_ENQUEUED,
	VTX_ST_OPEN,
	VTX_ST_VISITED
};

struct adjlist_dll {
	struct dll_node *head;
	struct dll_node *tail;
	size_t _list_len;

	enum vertex_st state;
	int color;
	long long distance;
	int parent;
	/*int fwd, bck;*/ /* dfs tree depth, >=1 unless uninitialized */
	/*int low;*/ /* lowpoint(), >=1 unless uninitialized */
	/*int chnum;*/ /* children count for this node */
};


struct edge {
	int a, b;
	long long weight;
	int index;
	char *used_ptr;
};

struct mst {
	struct vector *vec;
	long long tw;
};

struct unionfind {
	int *parent;
	int *rank;
	int _max;
};

/* {{{ function prototypes */
/* memory allocation wrappers */
void *s_calloc(size_t n, size_t size);
void *s_malloc(size_t size);
void *s_realloc(void *oldptr, size_t newsize);

struct queue *queue__new(const int n, const size_t elem_size);
int queue__push(struct queue *q, const void *p);
int queue__pop(struct queue *q, void *buf);
int queue__cleanup(struct queue *q);

/*
 * int vector_init(struct vector *v, int p);
 * int vector_append(struct vector *v, int a);
 * int vector_sort(struct vector *v, int (*cmpf)(const void *, const void *));
 * int vector_cleanup(struct vector *v);
 */

struct vector *vector__new(size_t elem_size, int p);
int vector__append(struct vector *v, const void *app);
char *vector__get_by_idx(struct vector *v, const int idx);
int vector__cleanup(struct vector *v);

struct dll_node *dll_insert(struct dll_node *node, struct dll_node *ins);
struct dll_node *dll_delete(struct dll_node *node);
void dll_mergesort(struct dll_node *head, int (*cmp)(const void *, const void *));

/* mergesort (with copy array optimization) */
void mergesort(void *base, size_t nmemb, size_t size,
		int (*cmpf)(const void *, const void *));

struct pqueue *pqueue__new(const size_t elem_size, int exp,
		const bool autoexpand, int (*f)(const void *, const void *));
int pqueue__insert(struct pqueue *pq, const void *elem);
int pqueue__extract(struct pqueue *pq, void *buf);
int pqueue__cleanup(struct pqueue *pq);

void adjl_dll_connect(struct adjlist_dll *, const int, const int, const long long);
void adjl_dll_cleanup(struct adjlist_dll *al);

/* misc */
struct dll_node *vector_to_dll_list(struct vector *v);
char *bytes_to_str(const void *ptr, const size_t size);

/* }}} */

/* {{{ memory allocation wrappers */
extern void *s_calloc(size_t n, size_t size)
{
	void *ptr;
	ptr = calloc(n, size);
	assert(ptr != NULL);
	if (ptr == NULL) {
		fprintf(stderr, "%s(): out of memory, failed to allocate %lu bytes\n",
				__func__, n * size);
		abort();
	}
	return ptr;
}

extern void *s_malloc(size_t size)
{
	void *ptr;
	ptr = malloc(size);
	assert(ptr != NULL);
	if (ptr == NULL) {
		fprintf(stderr, "%s(): out of memory, failed to allocate %lu bytes\n",
				__func__, size);
		abort();
	}
	return ptr;
}

extern void *s_realloc(void *oldptr, size_t newsize)
{
	void *newptr;
	newptr = realloc(oldptr, newsize);
	if (newptr == NULL) {
		fprintf(stderr, "%s(): out of memory, "
				"failed to realloc %p for new size of %lu bytes\n",
				__func__, oldptr, newsize);
		abort();
	}
	return newptr;
}
/* }}} */

/* {{{ queue */
extern struct queue *
queue__new(const int n, const size_t elem_size)
{
	struct queue *q = NULL;

	assert(n > 1);
	assert(elem_size > 0);

	q = (struct queue *) s_malloc(sizeof *q);
	q->data = (char *) s_calloc(n, elem_size);
	q->_data_size = elem_size;
	q->head = 0;
	q->n = 0;
	q->_max = n;

	return q;
}

extern int
queue__push(struct queue *q, const void *p)
{
	assert(q != NULL);
	assert(p != NULL);

	if (q->n >= q->_max) {
		debug_fprintf((stderr, "%s(): q->n (%d) >= q->_max (%d), can't push any deeper :-(\n",
				__func__, q->n, q->_max));
		return -1; /* can't push any further */
	}

	memcpy(q->data + ((q->head + q->n++) % q->_max) * q->_data_size, p, q->_data_size);
	debug_fprintf((stderr, "%s(): q->head=%d, q->n=%d\n",
			__func__, q->head, q->n));

	return 0;
}

extern int
queue__pop(struct queue *q, void *buf)
{
	assert(q != NULL);
	assert(buf != NULL);

	memcpy(buf, q->data + (q->head) * q->_data_size, q->_data_size);
	q->head = (q->head + 1) % q->_max;
	q->n--;
	debug_fprintf((stderr, "%s(): q->head=%d, q->n=%d\n",
			__func__, q->head, q->n));

	return 0;
}

extern int
queue__cleanup(struct queue *q)
{
	S_assert(q != NULL);
	if (q == NULL)
		return -1;

	if (q->_max == 0 || q->data == NULL)
		return 1;

	free(q->data);
	q->data = NULL;
	free(q);

	return 0;
}
/* }}} */

/* {{{ stack */
/* }}} */

/* {{{ autoarray */
extern struct vector *
vector__new(size_t elem_size, int p)
{
	struct vector *v = NULL;

	if (p < 0 || p >= (int) (CHAR_BIT * sizeof v->data[0]))
		p = 0;

	v = (struct vector *) s_malloc(sizeof *v);
	v->_max = 1 << p;
	v->_elem_size = elem_size;
	v->n = 0;
	v->data = (char *) s_calloc((size_t) v->_max, v->_elem_size);

	return v;
}

extern int
vector__append(struct vector *v, const void *app)
{
	int ret = 0;

	if (v == NULL) {
		fprintf(stderr, "%s(): received NULL ptr, not doing anything (-1)\n",
				__func__);
		return -1;
	}

	if (v->_max == 0) {
		/* weird input, fix it */
		ret |= 2;
		debug_fprintf((stderr, "%s(): v->_max is 0, which means that your "
					"autoarray (v=%p) is messed up. trying to fix this.\n",
					__func__, (void*) v));
		if (v->_elem_size == 0) {
			ret |= 4;
			fprintf(stderr, "%s(): can't fix this mess, bailing out (%d)\n",
					__func__, ret);
			return ret;
		} else {
			v->_max = 1;
			v->n = 0;
			v->data = (char *) s_calloc((size_t) v->_max, v->_elem_size);
		}
	}

	if (v->n + 1 >= v->_max) {
		v->data = (char *) s_realloc(v->data, v->_elem_size * (v->_max *= 2));
	}
	memcpy(v->data + (v->n++) * v->_elem_size, app, v->_elem_size);

	return ret;
}

extern char *
vector__get_by_idx(struct vector *v, const int idx)
{
	if (v == NULL) {
		fprintf(stderr, "%s(): received NULL ptr, not doing anything (NULL)\n",
				__func__);
		return NULL;
	}

	if (v->_elem_size == 0) {
		fprintf(stderr, "%s(): whoah, looks like your vector is messed up big time (NULL)\n",
				__func__);
		return NULL;
	}

	if (idx < 0 || idx >= v->n) {
		fprintf(stderr, "%s(): index out of range %d (v->n=%d)\n",
				__func__, idx, v->n);
		return NULL;
	}

	return v->data + (idx) * v->_elem_size;
}

extern int
vector__cleanup(struct vector *v)
{
	int ret = 0;

	if (v == NULL) {
		fprintf(stderr, "%s(): received NULL ptr, not doing anything (-1)\n",
				__func__);
		return -1;
	}

	if (v->_max > 0) {
		v->_max = v->n = 0;
		free(v->data);
		v->data = NULL;
	} else {
		ret |= 1;
	}

	/* TODO: improve logic */
	debug_fprintf((stderr, "%s(): freeing v=%p\n", __func__, (void*) v));
	free(v);

	return ret;
}
/* }}} */

/* {{{ singly-linked list */
/* TODO: include sorting of a linked list */
/* }}} */

/* {{{ doubly-linked list */
/*
 * This function inserts one node pointed to by 'ins' _after_ 'node'.
 */
extern struct dll_node *
dll_insert(struct dll_node *node, struct dll_node *ins)
{
	assert(node != NULL);
	if (ins == NULL) {
		debug_fprintf((stderr, "dll_insert(): ins is NULL, not doing anything\n"));
		return node;
	}

	if (node->next) {
		assert(node->next->prev == node);
		node->next->prev = ins;
	}
	ins->next = node->next;
	ins->prev = node;
	node->next = ins;
	return ins;
}

/*
 * This function extracts 'node' from a doubly-linked list and returns pointer
 * to that node, pointers '->prev' and '->next' are not reset.
 *
 * If you really want to get rid of a node, call
 * 	free(dll_delete(unneeded_node));
 */
extern struct dll_node *
dll_delete(struct dll_node *node)
{
	if (!node) {
		debug_fprintf((stderr, "dll_delete(): received NULL ptr, wtf am i supposed to delete?\n"));
		return NULL;
	}

	if (node->prev) {
		assert(node->prev->next == node);
		node->prev->next = node->next;
	}
	if (node->next) {
		assert(node->next->prev == node);
		node->next->prev = node->prev;
	}

	return node;
}

/*
 * Merge-sort for doubly-linked list.
 *
 * TODO: work out the use of (*cmp)() function
 */
extern void
dll_mergesort(struct dll_node *head, int (*cmp)(const void *, const void *))
{
	struct dll_node *end, *mid;
	struct dll_node *sorted, *first, *second;
	struct dll_node *swap;

	if (head == NULL || head->next == NULL) /* lengths 0, 1 */
		return;

	end = mid = head;
	while (end && end->next && end->next->next) {
		end = end->next->next;
		mid = mid->next;
	}
	if (end && end->next) {
		end = end->next;
		mid = mid->next;
	}

	mid->prev->next = NULL;
	mid->prev = NULL;
	dll_mergesort(head, cmp);
	dll_mergesort(mid, cmp);

	if (cmp(head->data, mid->data) > 0) { /* this is the tricky part */
		char *t1;
		size_t t2;
		struct dll_node *t3;
		int t4;
#define SWAP_(a,b,t) do{(t)=(a),(a)=(b),(b)=(t);}while(0)
		if (head->next && mid->next)
			SWAP_(head->next->prev, mid->next->prev, t3);
		SWAP_(head->x, mid->x, t4);
		SWAP_(head->data, mid->data, t1);
		SWAP_(head->_data_size, mid->_data_size, t2);
		SWAP_(head->prev, mid->prev, t3);
		SWAP_(head->next, mid->next, t3);
#undef SWAP_
	}

	/*
	 * from now on using only ->prev and ->next pointers should suffice us
	 */
	first = head->next;
	if (first) first->prev = NULL;
	second = mid;

	sorted = head;
	sorted->next = NULL;
	assert(sorted->prev == NULL);

	while (first && second) {
		assert(sorted->next == NULL);

		/* TODO: un-copypaste this code (use 'swap' ptr) */
		if (cmp(first->data, second->data) < 0)
			swap = first;
		else
			swap = second;

		assert(swap->prev == NULL);

		sorted->next = swap;
		swap->prev = sorted;
		sorted = swap;

		swap = swap->next;
		if (swap) {
			assert(swap->prev == sorted);
			swap->prev->next = NULL;
			swap->prev = NULL;
		}
	}
	assert(sorted->next == NULL);
	if (first) {
		assert(first->prev == NULL);
		sorted->next = first;
		first->prev = sorted;
	}
	if (second) {
		assert(second->prev == NULL);
		sorted->next = second;
		second->prev = sorted;
	}
}
/* }}} */

/* {{{ mergesort (with copy array optimization) */
static void
mergesort__merge(void *p1, size_t nmemb, size_t size,
		int (*cmpf)(const void *, const void *),
		void *p2, const int depth,
		size_t L, size_t M, size_t R)
{
	register char *base, *cpybuf;
	size_t i = L, j = M + 1;
	register size_t s = 0; /* points to where we will place next element */

	if (depth & 1)
		base = p1, cpybuf = p2;
	else
		base = p2, cpybuf = p1;

	while (i <= M && j <= R) {
		if (cmpf(base + i * size, base + j * size) <= 0) {
			if (i <= M) {
				memcpy(cpybuf + s*size, base + i*size, size);
				s++;
				i++;
			} else if (j <= R) {
				memcpy(cpybuf + s*size, base + j*size, size);
				s++;
				j++;
			}
		} else {
			if (j <= R) {
				memcpy(cpybuf + s*size, base + j*size, size);
				s++;
				j++;
			} else if (i <= M) {
				memcpy(cpybuf + s*size, base + i*size, size);
				s++;
				i++;
			}
		}
	}

	/*
	 * let's see how this works
	 */
	while (i <= M)
		memcpy(cpybuf + (s++) * size, base + (i++) * size, size);
	while (j <= R)
		memcpy(cpybuf + (s++) * size, base + (j++) * size, size);
}

static void
mergesort__main(void *base, size_t nmemb, size_t size,
		int (*cmpf)(const void *, const void *),
		void *cpybuf, const int depth,
		size_t L, size_t R)
{
	size_t M = (L + R) / 2;

	if (L < R) {
		mergesort__main(base, nmemb, size, cmpf, cpybuf, depth + 1, L, M);
		mergesort__main(base, nmemb, size, cmpf, cpybuf, depth + 1, M + 1, R);
		mergesort__merge(base, nmemb, size, cmpf, cpybuf, depth, L, M, R);
	}
}

extern void
mergesort(void *base, size_t nmemb, size_t size,
		int (*cmpf)(const void *, const void *))
{
	void *cpybuf;

	cpybuf = s_malloc(nmemb * size);
	memcpy(cpybuf, base, nmemb * size);
	mergesort__main(base, nmemb, size, cmpf, cpybuf, 0,
			0UL, nmemb - 1UL);
	free(cpybuf);
}
/* }}} */

/* {{{ priority queue */
/* {{{ heap mng */
/*
 * TODO: generalize these functions
 */
static int
pqueue__heap_sift_down(struct pqueue *pq, int idx)
{
	register int swap;
	int parent = idx, child;

	while (parent * 2 + 1 < pq->n) {
		child = parent * 2 + 1;
		swap = parent;

		if ((*pq->cmp)(pq->data + (parent) * pq->_data_size,
		               pq->data + (child) * pq->_data_size) > 0) {
			swap = child;
		}

		if (child + 1 < pq->n &&
		    (*pq->cmp)(pq->data + (swap) * pq->_data_size,
		               pq->data + (child + 1) * pq->_data_size) > 0) {
			swap = child + 1;
		}

		if (swap != parent) {
#ifdef DEBUG
			char *_bytes = bytes_to_str(pq->data + (parent) * pq->_data_size,
										pq->_data_size);
			fprintf(stderr, "%s(): swapping (%s) with ", __func__, _bytes);
			free(_bytes);
			_bytes = bytes_to_str(pq->data + (swap) * pq->_data_size,
							pq->_data_size);
			fprintf(stderr, "(%s)\n", _bytes);
			free(_bytes);
#endif
			memmove(pq->data + (pq->n) * pq->_data_size,
					pq->data + (parent) * pq->_data_size,
					pq->_data_size);
			memmove(pq->data + (parent) * pq->_data_size,
					pq->data + (swap) * pq->_data_size,
					pq->_data_size);
			memmove(pq->data + (swap) * pq->_data_size,
					pq->data + (pq->n) * pq->_data_size,
					pq->_data_size);
			parent = swap;
		} else {
			return 1;
		}
	}

	return 2;
}

static int
pqueue__heap_sift_up(struct pqueue *pq, int idx)
{
	int child = idx, parent = (idx - 1) / 2;

	while (child > 0) {
		if ((*pq->cmp)(pq->data + (parent) * pq->_data_size,
						pq->data + (child) * pq->_data_size) > 0) {
#ifdef DEBUG
			char *_bytes = bytes_to_str(pq->data + (parent) * pq->_data_size,
										pq->_data_size);
			fprintf(stderr, "%s(): swapping (%s) with ", __func__, _bytes);
			free(_bytes);
			_bytes = bytes_to_str(pq->data + (child) * pq->_data_size,
							pq->_data_size);
			fprintf(stderr, "(%s)\n", _bytes);
			free(_bytes);
#endif
			memmove(pq->data + (pq->n) * pq->_data_size,
					pq->data + (parent) * pq->_data_size,
					pq->_data_size);
			memmove(pq->data + (parent) * pq->_data_size,
					pq->data + (child) * pq->_data_size,
					pq->_data_size);
			memmove(pq->data + (child) * pq->_data_size,
					pq->data + (pq->n) * pq->_data_size,
					pq->_data_size);

			child = parent--;
			parent /= 2;
		} else {
			return 1;
		}
	}

	return 2;
}
/* }}} */
/*
 * Returns an initialized pqueue
 */
extern struct pqueue *
pqueue__new(const size_t elem_size, int exp, const bool autoexpand,
		int (*f)(const void *, const void *))
{
	struct pqueue *pq;

	/* if (f == NULL) f = &numcmp; default to integers */
	if (exp <= 0) exp = 6; /* default to 64 elements */
	S_assert(exp <= 23); /* 8,388,608 elements _might_ be a little too much */
	assert(elem_size != 0);

	pq = s_malloc(sizeof *pq);
	pq->data = s_calloc((pq->_max = 1<<exp), (pq->_data_size = elem_size));
	pq->n = 0;
	pq->cmp = f;
	pq->_autoexpand = autoexpand; /* TODO */

	return pq;
}

/*
 * Insert element that 'elem' points to into the pqueue.
 */
extern int
pqueue__insert(struct pqueue *pq, const void *elem)
{
	char *tmp = NULL;

	if (pq == NULL) {
		fprintf(stderr, "%s(): pq == NULL, not doing anything (-2)\n", __func__);
		return -2;
	}

	if (elem == NULL) {
		fprintf(stderr, "%s(): elem == NULL, what am i supposed to insert? (-1)\n", __func__);
		return -1;
	}

	if (pq->n + 1 >= pq->_max) {
		/* i betcha the ">=" makes you wonder .. */
		tmp = s_realloc(pq->data, (pq->_max <<= 1) * pq->_data_size);
		assert(tmp != NULL);
		pq->data = tmp;
	}
	memcpy(pq->data + (pq->_data_size * pq->n), elem, pq->_data_size);

	pqueue__heap_sift_up(pq, pq->n++);

	return 0;
}

/*
 * Extract the top element from the pqueue and put it into 'obuf' buffer.
 */
extern int
pqueue__extract(struct pqueue *pq, void *buf)
{
	if (pq == NULL) {
		fprintf(stderr, "%s(): received a NULL ptr, not doing anything (-1)\n", __func__);
		return -1;
	}

	if (buf != NULL)
		memcpy(buf, pq->data, pq->_data_size);
	memmove(pq->data, pq->data + (--pq->n) * pq->_data_size, pq->_data_size);
	pqueue__heap_sift_down(pq, 0);

	return 0;
}

extern int
pqueue__cleanup(struct pqueue *pq)
{
	if (pq == NULL) {
		fprintf(stderr, "%s(): received a NULL ptr, not doing anything (-1)\n", __func__);
		return -1;
	}

	if (pq->_max > 0) {
		free(pq->data);
		pq->data = NULL;
	}
	free(pq);

	return 0;
}
/* }}} */

/* {{{ graph repr: adjlist w/ doubly-linked list */
extern void
adjl_dll_connect(struct adjlist_dll *node, const int conid, const int edgeid,
		const long long weight)
{
	struct dll_node *Wilson;

	Wilson = (struct dll_node *) s_calloc(1, sizeof *Wilson);
	Wilson->x = conid;
	Wilson->y = edgeid;
	Wilson->z = weight;
	Wilson->prev = Wilson->next = NULL;

	if (node->head == NULL) {
		assert(node->tail == NULL);
		node->head = node->tail = Wilson;
		node->_list_len = 1;
	} else {
		node->tail = dll_insert(node->tail, Wilson);
		node->_list_len++;
	}
}

extern void
adjl_dll_cleanup(struct adjlist_dll *al)
{
	struct dll_node *nx = al->head, *pr = al->head;

	while (nx) {
		pr = nx;
		nx = nx->next;
		free(pr);
	}
	al->_list_len = 0;
	al->head = al->tail = NULL;
}
/* }}} */

/* {{{ misc */
extern struct dll_node *
vector_to_dll_list(struct vector *v)
{
	struct dll_node *head = NULL, *tail = NULL;
	struct dll_node *next;
	register int i;

	if (v == NULL || v->_max == 0 || v->n == 0)
		return NULL;

	head = tail = s_calloc(1UL, sizeof *head);
	head->x = v->data[0];

	for (i = 1; i < v->n; i++) {
		next = s_calloc(1UL, sizeof *next);
		next->x = v->data[i];
		tail = dll_insert(tail, next);
	}

	return head;
}

extern char *
bytes_to_str(const void *ptr, const size_t size)
{
	char *str;
	const unsigned char *byte = ptr;
	int offset;

	/* each byte is represented as "0x??" and a
	 * whitespace character in between */
	str = s_malloc(5 * size + 1);
	for (offset = 0; offset < size; offset++) {
		sprintf(str + offset * 5, "0x%02hhx ", byte[offset]);
	}
	str[size * 5 - 1] = '\0';

	return str;
}
/* }}} */

/* {{{ @@@ union-find dataset @@@ */
void
uf__make_set(struct unionfind *uf, const int x)
{
	uf->parent[x] = x;
	uf->rank[x] = 0;
}

int
uf__find_set(struct unionfind *uf, const int x)
{
	if (x == uf->parent[x])
		return x;
	return uf->parent[x] = uf__find_set(uf, uf->parent[x]);
}

void
uf__union(struct unionfind *uf, int x, int y)
{
	x = uf__find_set(uf, x);
	y = uf__find_set(uf, y);
	if (x != y) {
		if (uf->rank[x] < uf->rank[y])
			SWAP_INT(x, y);
		uf->parent[y] = x;
		if (uf->rank[x] == uf->rank[y])
			uf->rank[x]++;
	}
}
/* }}} */

int
edgecmp(const void *p1, const void *p2)
{
	const struct edge *e1 = p1, *e2 = p2;

	assert(p1 != NULL && p2 != NULL);
	if (e1->weight < e2->weight)
		return -1;
	if (e1->weight > e2->weight) /* FML :( */
		return 1;
	return 0;
}

int
kruskal(struct adjlist_dll *al, const int n, struct mst *mst, struct pqueue *E)
{
	/*struct dll_node *nd;*/
	struct unionfind V;
	register int i;
	struct edge e;
	int tmp, ret = 0;

	V.parent = s_calloc(n, sizeof V.parent[0]);
	V.rank = s_calloc(n, sizeof V.rank[0]);
	V._max = n;

	for (i = 0; i < n; i++)
		uf__make_set(&V, i);

	while (E->n) {
		pqueue__extract(E, &e);

		debug_fprintf((stderr, "%s(): E->n=%d, e = { a=%d, b=%d, "
				"weight=%lld, index=%d, "
				"used_ptr=%p(=%c) }\n",
				__func__, E->n, e.a, e.b, e.weight, e.index,
				e.used_ptr, (e.used_ptr == NULL ? '@' : *e.used_ptr + '0')));

		if (uf__find_set(&V, e.a) != uf__find_set(&V, e.b)) {
			/* add edge to the minimal spanning tree */
			vector__append(mst->vec, &e.index);
			mst->tw += e.weight;

			/* merge */
			uf__union(&V, e.a, e.b);

			/* pre-caution */
			*e.used_ptr = 1;
		}
	}

	tmp = uf__find_set(&V, 0);
	for (i = 0; i < n; i++) {
		if (uf__find_set(&V, i) != tmp) {
			/*
			 * i'th and 0 vertexes are in different connection spaces
			 * which means that there's no mst for this graph
			 */
			/* bail out */
			ret |= 1;
			break;
		}
	}

	free(V.parent);
	free(V.rank);
	V._max = 0;

	return ret;
}

int
main(int argc, char **argv)
{
	struct adjlist_dll *al;
	struct pqueue *E;
	struct mst mst;
	struct edge e;
	int i, n, m;
	char *used;

	mst.vec = vector__new(sizeof 0xD, 0);
	mst.tw = 0LL;
	E = pqueue__new(sizeof (struct edge), 4, true, &edgecmp);

	scanf("%d %d", &n, &m);
	al = s_calloc(n, sizeof *al);
	used = s_calloc(2 * m, sizeof *used);

	for (i = 0; i < m; i++) {
		scanf("%d %d %lld", &e.a, &e.b, &e.weight);
		e.a--;
		e.b--;
		e.index = i;
		e.used_ptr = used + i;

		pqueue__insert(E, &e);
		adjl_dll_connect(al + e.a, e.b, i, e.weight);
		adjl_dll_connect(al + e.b, e.a, i, e.weight);

		al[e.a].tail->data = al[e.b].tail->data = used + i;
	}

	if (kruskal(al, n, &mst, E) == 0) {
		printf("%lld\n", mst.tw);
		/*
		for (i = 0; i < mst.vec->n; i++) {
			printf(" %d\n", 1 + *(int*)vector__get_by_idx(mst.vec, i));
		}
		*/
	} else {
		puts("0");
	}

	vector__cleanup(mst.vec);
	pqueue__cleanup(E);
	for (i = 0; i < n; i++) adjl_dll_cleanup(al + i);
	free(al);
	free(used);
	return 0;
}
